package com.jzoffer;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/*
* 给定一棵二叉搜索树，请找出其中的第k小的结点。
* 例如， （5，3，7，2，4，6，8）    中，
* 按结点数值大小顺序第三小结点的值为4。
* */
public class FindKthSortBinaryTree {
    public static void main(String[] args)  throws IOException {
        TreeNode t1 = new TreeNode(5);
        TreeNode t2 = new TreeNode(4);
        TreeNode t3 = new TreeNode(2);
        TreeNode t4 = new TreeNode(3);
        TreeNode t5 = new TreeNode(7);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(8);
        t1.left = t2;
        t2.left = t3;
        t3.right = t4;
        t1.right = t5;
        t5.left = t6;
        t5.right = t7;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int k = Integer.parseInt(str);
        TreeNode treeNode = kthNode(t1, k);
        System.out.println(treeNode.val);
        br.close();

    }

    public static TreeNode kthNode(TreeNode pRoot, int k){
        if(pRoot == null || k < 1){
            return null;
        }
        TreeNode node = pRoot;
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        while (node != null || !stack.isEmpty()){
            if(node != null){
                stack.push(node);
                node = node.left;
            }else{
                node = stack.pop();
                count++;
                if(count == k){
                    return node;
                }
                node = node.right;

            }
        }
        return null;
    }
}
